//编写一个程序，通过填充空格来解决数独问题。 
//
// 数独的解法需 遵循如下规则： 
//
// 
// 数字 1-9 在每一行只能出现一次。 
// 数字 1-9 在每一列只能出现一次。 
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 
// 
//
// 数独部分空格内已填入了数字，空白格用 '.' 表示。 
//
// 
//
// 
// 
// 
// 示例： 
//
// 
//输入：board =
// [["5","3",".",".","7",".",".",".","."],
// ["6",".",".","1","9","5","." ,".","."],
// [".","9","8",".",".",".",".","6","."],
// ["8",".",".",".","6",".",".","." ,"3"],
// ["4",".",".","8",".","3",".",".","1"],
// ["7",".",".",".","2",".",".",".","6" ],
// [".","6",".",".",".",".","2","8","."],
// [".",".",".","4","1","9",".",".","5"],
// [" .",".",".",".","8",".",".","7","9"]]
//输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"
//],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["
//4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","
//6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","
//5","2","8","6","1","7","9"]]
//解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
//
//
// 
//
// 
//
// 提示： 
//
// 
// board.length == 9 
// board[i].length == 9 
// board[i][j] 是一位数字或者 '.' 
// 题目数据 保证 输入数独仅有一个解 
// 
// 
// 
// 
// Related Topics 数组 回溯 矩阵 
// 👍 1109 👎 0


package leetcode.editor.cn.lc37;

import java.util.Arrays;

public class SudokuSolver {
    public static void main(String[] args) {
        Solution solution = new Solution();

        char[][] b = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        solution.solveSudoku(b);
        for (char[] chars : b) {
            System.out.println(Arrays.toString(chars));
        }

    }
}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    static final int N = 9;
    static final int INNER_N = 3;
    static final char BASE = '0';
    static final char EMPTY = '.';

    public void solveSudoku(char[][] board) {
        int blankCount = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                blankCount++;
            }
        }
        boolean solve = solve(board, blankCount);
        if (!solve) {
            throw new IllegalStateException();
        }
    }

    private boolean solve(char[][] board, int blankCount) {

        BoardImage boardImage = new BoardImage(board);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] != EMPTY) {
                    continue;
                }

                int[] available = new int[10];

                for (int k = 0; k < N; k++) {
                    char h = board[i][k];
                    char v = board[k][j];
                    if (h != EMPTY) {
                        available[h - BASE]++;
                    }
                    if (v != EMPTY) {
                        available[v - BASE]++;
                    }
                }

                // 小方块内
                int sqh = i / 3 * 3;
                int sqv = j / 3 * 3;
                for (int m = sqh; m < sqh + 3; m++) {
                    for (int n = sqv; n < sqv + 3; n++) {
                        char c = board[m][n];
                        if (c != EMPTY) {
                            available[c - BASE]++;
                        }
                    }
                }

                boolean noCandidate = true;

                for (int ai = 0; ai < available.length; ai++) {
                    int av = available[ai];
                    if (av == 0) {
                        noCandidate = false;
                        board[i][j] = (char) (ai + BASE);
                        boardImage.print();
                        blankCount--;
                        if (blankCount == 0) {
                            return true;
                        }
                        boolean solve = solve(board, blankCount);
                        if (solve) {
                            return true;
                        }
                    }
                }
                //无
                if (noCandidate) {
                    return false;
                }else {
                    board[i][j] = EMPTY;
                    blankCount++;
                }
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

class BoardImage{
    public BoardImage(char[][] board) {
        this.board = board;
    }

    char[][] board;

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (char[] chars : board) {
            for (char aChar : chars) {
                stringBuilder.append("  ").append(aChar);
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    public void print(){
        System.out.println(toString());
    }
}